﻿#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<set>
#include<vector>
using namespace std;

void testinsert()
{
	// 去重+升序
	set<int> st;
	// 去重 + 降序(给一个大于的仿函数)
	//set<int, greater<int>> s;
	
	st.insert(4);
	st.insert(4);
	st.insert(5);
	st.insert(2);
	st.insert(9);
	st.insert(6);

	auto it = st.begin();
	while (it != st.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	st.insert({ 2,1,4,5,7 });

	for (auto e : st)
	{
		cout << e << " ";
	}
	cout << endl;


	set<string> strset = { "left","insert","erase" };

	for (auto s : strset)
	{
		cout << s << " ";
	}
	cout << endl;
}

void testerase()
{
	set<int> s = { 4,2,7,2,8,5,9 };
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	
	// 删除最⼩值
	s.erase(s.begin());
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	// 直接删除x
	int x;
	cin >> x;
	size_t num = s.erase(x); // 删除val，val不存在返回0，存在返回1
	if (num == 0)
	{
		cout << "该元素不存在" << endl;
	}

	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	// 直接查找在利用迭代器删除x
	cin >> x;
	auto pos = s.find(x); // 删除⼀个迭代器位置的值
	if (pos != s.end())
	{
		s.erase(pos);
	}
	else
	{
		cout << x << "不存在！" << endl;
	}
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
}

void testfind()
{
	set<int> s = { 40,20,70,20,80,50,90 };
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	
	int x;
	cin >> x;
	// 算法库的查找 O(N)
	auto pos1 = find(s.begin(), s.end(), x);
	// set⾃⾝实现的查找 O(logN)
	auto pos2 = s.find(x);
	
	// 利用count间接实现快速查找
	if (s.count(x))
	{
		cout << x << "在！" << endl;
	}
	else
	{
		cout << x << "不存在！" << endl;
	}

	// 实现查找到的[itlow,itup)包含[30, 60]区间
	// 返回 >= 30
	auto itlow = s.lower_bound(30); // 该函数将返回一个不小于val的第一个元素的迭代器
	// 返回 > 60
	auto itup = s.upper_bound(60); // 该函数会向大于val的第一个元素返回一个迭代器
	
	// 删除这段区间的值
	s.erase(itlow, itup);
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
}

void testmultiset()
{
	// 相⽐set不同的是，multiset是排序，但是不去重
	multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 };
	auto it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	// 相⽐set不同的是，x可能会存在多个，find查找中序的第⼀个
	int x;
	cin >> x;
	auto pos = s.find(x);
	while (pos != s.end() && *pos == x)
	{
		cout << *pos << " ";
		++pos;
	}
	cout << endl;
	// 相⽐set不同的是，count会返回x的实际个数
	cout << s.count(x) << endl;
	// 相⽐set不同的是，erase给值时会删除所有的x
	s.erase(x);
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
}

//int main()
//{
//	testmultiset();
//	return 0;
//}

struct ListNode 
{
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};
 
// 环形链表
class Solution {
public:
	ListNode* detectCycle(ListNode* head) {
		set<ListNode*> s;

		ListNode* cur = head;
		while (cur)//一个一个插入
		{
			// 返回值：1.插入位置的迭代器 2.插入的布尔值
			auto ret = s.insert(cur);
			if (ret.second == 0)
				return cur;// 重复位置就是入环节点
			cur = cur->next;
		}
		return nullptr;
	}
};

// 两个相交数组
class Solution {
public:
	vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
	{
		// 先放到set里去重
		set<int> s1(nums1.begin(), nums1.end());
		set<int> s2(nums2.begin(), nums2.end());

		// 两个指针分别指向两个数组，比较大小，小的++，相等的就是交集
		auto p1 = s1.begin();
		auto p2 = s2.begin();
		vector<int> res;

		while (p1 != s1.end() && p2 != s2.end())
		{
			if (*p1 > *p2)
				++p2;
			else if (*p1 < *p2)
				++p1;
			else
			{
				res.push_back(*p1);
				++p1;
				++p2;
			}
		}
		return res;
	}
};

#include<iostream>
#include<map>
using namespace std;
int main()
{
	// initializer_list构造及迭代遍历
	map<string, string> dict = { {"left", "左边"}, {"right", "右边"},
	{"insert", "插入"},{ "string", "字符串" } };
	
	//map<string, string>::iterator it = dict.begin();
	auto it = dict.begin();
	while (it != dict.end())
	{
		// map的迭代基本都使用operator->,这⾥省略了一个->
		// 第一个->是迭代器运算符重载，返回pair*，第二个箭头是结构指针解引用取pair数据
		//cout << it.operator->()->first << ":" << it.operator->()-> second << endl;
		cout << it->first << ":" << it->second << endl;
		++it;
	}
	cout << endl;
	
	// insert插入pair对象的4种方式，对比之下，最后一种最⽅便
	pair<string, string> kv1("first", "第一个");
	dict.insert(kv1);
	dict.insert(pair<string, string>("second", "第⼆个"));
	dict.insert(make_pair("sort", "排序"));
	dict.insert({ "auto", "自动的" });
	
	// "left"已经存在，插入失败
	dict.insert({ "left", "左边，剩余" });
	// 范围for遍历
	for (const auto& e : dict)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << endl;
	
	string str;
	while (cin >> str)
	{
		auto ret = dict.find(str);
		if (ret != dict.end())
		{
			cout << "->" << ret->second << endl;
		}
		else
		{
			cout << "无此单词，请重新输⼊" << endl;
		}
	}
	return 0;
}

#include<iostream>
#include<map>
#include<string>
using namespace std;
int main()
{
	map<string, string> dict;
	dict.insert(make_pair("sort", "排序"));
	// key不存在->插⼊ {"insert", string()}
	dict["insert"];
	// 插入+修改
	dict["left"] = "左边";
	// 修改
	dict["left"] = "左边、剩余";
	// key存在->查找
	cout << dict["left"] << endl;

	// 利⽤[]插入+修改功能，巧妙实现统计谁水果出现的次数
	string arr[] = { "苹果", "西⽠", "苹果", "西⽠", "苹果", "苹果", "西⽠",
	"苹果", "⾹蕉", "苹果", "⾹蕉" };
	map<string, int> countMap;
	for (const auto& str : arr)
	{
		// []先查找⽔果在不在map中
		// 1、不在，说明水果第一次出现，则插入{水果, 0}，同时返回次数的引用，++一下就变成1次了
		// 2、在，则返回⽔果对应的次数++
		countMap[str]++;

	}
	for (const auto& e : countMap)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << endl;
	
	return 0;
}




// oj 
//class Solution {
//public:
//	// 仿函数控制升序
//	struct Compare
//	{
//		bool operator()(const pair<string, int>& x, const pair<string, int>& y)
//		{
//			return x.second > y.second;
//		}
//	};
//
//	vector<string> topKFrequent(vector<string>& words, int k) {
//		// 1.放入map实现按字典序排序
//		map<string, int> mp;
//		for (auto w : words)
//		{
//			mp[w]++; // 存在->++ ; 不存在->插入
//		}
//		// 2.放入vector实现按次数排序
//		vector<pair<string, int>> vv(mp.begin(), mp.end());
//		// 要用稳定的排序stable_sort,sort底层是快排，是不稳定的
//		stable_sort(vv.begin(), vv.end(), Compare());
//
//		// 3.取前k个
//		vector<string> v;
//		for (int i = 0; i < k; i++)
//		{
//			v.push_back(vv[i].first);
//		}
//		return v;
//	}
//};

// oj
//class Solution {
//public:
//	map<Node*, Node*> mp;
//
//	Node* copyRandomList(Node* head)
//	{
//		if (head == nullptr)
//			return nullptr;
//
//		if (!mp.count(head))
//		{
//			Node* copy = new Node(head->val);
//			mp[head] = copy;
//
//			copy->next = copyRandomList(head->next);
//			// 上一行代码的回溯结束后，已经将所有原节点与拷贝节点
//			//建立映射关系并插入map里了
//
//			// 1.下一行的所有回溯不会进入if语句里，
//			// 而是执行最后一行返回语句,回溯上来就是mp[head->random]
//			// 2.[]作用是在map中查找head的random指向的节点
//			// 3. 将拷贝链表random指针指向该节点
//			copy->random = copyRandomList(head->random);
//		}
//		return mp[head];
//	}
//};
//class Solution {
//public:
//	Node* copyRandomList(Node* head)
//	{
//		Node* cur = head;
//		Node* copyhead = nullptr;
//		Node* copytail = nullptr;
//		map<Node*, Node*> mp;
//
//		// 1、先将这些原节点放到map里(next顺序)
//		while (cur)
//		{
//			if (copytail == nullptr)
//			{ // 拷贝第一个节点
//				copyhead = copytail = new Node(cur->val);
//			}
//			else
//			{
//				copytail->next = new Node(cur->val);
//				copytail = copytail->next;
//			}
//			// 原节点cur和拷贝节点coptail -> kv存储
//			// mp 中没有cur，插入<cur,copytail>
//			// 插入的cur仍会保留其特性(next,random,val)
//			mp[cur] = copytail;
//			cur = cur->next;
//		}
//
//		// 2、处理copy链表的random指针
//		cur = head; // 重新指向原头
//		Node* copycur = copyhead;
//		while (cur)
//		{
//			if (cur->random == nullptr)
//			{
//				copycur->random = nullptr;
//			}
//			else
//			{   // 映射关系，查找功能
//				// 1.[]查找cur的random指针指向的节点(在map中)
//				// 2.将拷贝链表random指针指向该节点
//				copycur->random = mp[cur->random];
//			}
//			cur = cur->next;
//			copycur = copycur->next;
//		}
//
//		return copyhead;
//	}
//};